First half of LWG#2354: 'Unnecessary copying when inserting into maps with braced-init syntax' git-svn-id: https://llvm.org/svn/llvm-project/libcxx/trunk@256859 91177308-0d34-0410-b5e6-96231b3b80d8
diff --git a/include/__tree b/include/__tree index cb58a90..94565bc 100644 --- a/include/__tree +++ b/include/__tree
@@ -909,6 +909,13 @@ iterator __insert_multi(const value_type& __v); iterator __insert_multi(const_iterator __p, const value_type& __v); +#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES + pair<iterator, bool> __insert_unique( value_type&& __v); + iterator __insert_unique(const_iterator __p, value_type&& __v); + iterator __insert_multi( value_type&& __v); + iterator __insert_multi(const_iterator __p, value_type&& __v); +#endif + pair<iterator, bool> __node_insert_unique(__node_pointer __nd); iterator __node_insert_unique(const_iterator __p, __node_pointer __nd); @@ -1730,6 +1737,28 @@ #endif // _LIBCPP_HAS_NO_VARIADICS template <class _Tp, class _Compare, class _Allocator> +pair<typename __tree<_Tp, _Compare, _Allocator>::iterator, bool> +__tree<_Tp, _Compare, _Allocator>::__insert_unique(value_type&& __v) +{ + __node_holder __h = __construct_node(_VSTD::forward<value_type>(__v)); + pair<iterator, bool> __r = __node_insert_unique(__h.get()); + if (__r.second) + __h.release(); + return __r; +} + +template <class _Tp, class _Compare, class _Allocator> +typename __tree<_Tp, _Compare, _Allocator>::iterator +__tree<_Tp, _Compare, _Allocator>::__insert_unique(const_iterator __p, value_type&& __v) +{ + __node_holder __h = __construct_node(_VSTD::forward<value_type>(__v)); + iterator __r = __node_insert_unique(__p, __h.get()); + if (__r.__ptr_ == __h.get()) + __h.release(); + return __r; +} + +template <class _Tp, class _Compare, class _Allocator> template <class _Vp> pair<typename __tree<_Tp, _Compare, _Allocator>::iterator, bool> __tree<_Tp, _Compare, _Allocator>::__insert_unique(_Vp&& __v) @@ -1754,6 +1783,28 @@ } template <class _Tp, class _Compare, class _Allocator> +typename __tree<_Tp, _Compare, _Allocator>::iterator +__tree<_Tp, _Compare, _Allocator>::__insert_multi(value_type&& __v) +{ + __node_base_pointer __parent; + __node_base_pointer& __child = __find_leaf_high(__parent, __v); + __node_holder __h = __construct_node(_VSTD::forward<value_type>(__v)); + __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get())); + return iterator(__h.release()); +} + +template <class _Tp, class _Compare, class _Allocator> +typename __tree<_Tp, _Compare, _Allocator>::iterator +__tree<_Tp, _Compare, _Allocator>::__insert_multi(const_iterator __p, value_type&& __v) +{ + __node_base_pointer __parent; + __node_base_pointer& __child = __find_leaf(__p, __parent, __v); + __node_holder __h = __construct_node(_VSTD::forward<value_type>(__v)); + __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get())); + return iterator(__h.release()); +} + +template <class _Tp, class _Compare, class _Allocator> template <class _Vp> typename __tree<_Tp, _Compare, _Allocator>::iterator __tree<_Tp, _Compare, _Allocator>::__insert_multi(_Vp&& __v) diff --git a/include/map b/include/map index 2416205..87add43 100644 --- a/include/map +++ b/include/map
@@ -126,9 +126,11 @@ template <class... Args> iterator emplace_hint(const_iterator position, Args&&... args); pair<iterator, bool> insert(const value_type& v); + pair<iterator, bool> insert( value_type&& v); // C++17 template <class P> pair<iterator, bool> insert(P&& p); iterator insert(const_iterator position, const value_type& v); + iterator insert(const_iterator position, value_type&& v); // C++17 template <class P> iterator insert(const_iterator position, P&& p); template <class InputIterator> @@ -336,9 +338,11 @@ template <class... Args> iterator emplace_hint(const_iterator position, Args&&... args); iterator insert(const value_type& v); + iterator insert( value_type&& v); // C++17 template <class P> iterator insert(P&& p); iterator insert(const_iterator position, const value_type& v); + iterator insert(const_iterator position, value_type&& v); // C++17 template <class P> iterator insert(const_iterator position, P&& p); template <class InputIterator> @@ -1089,6 +1093,17 @@ insert(const_iterator __p, const value_type& __v) {return __tree_.__insert_unique(__p.__i_, __v);} +#if _LIBCPP_STD_VER > 14 && !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) + _LIBCPP_INLINE_VISIBILITY + pair<iterator, bool> + insert( value_type&& __v) {return __tree_.__insert_unique(_VSTD::forward<value_type>(__v));} + + _LIBCPP_INLINE_VISIBILITY + iterator + insert(const_iterator __p, value_type&& __v) + {return __tree_.__insert_unique(__p.__i_, _VSTD::forward<value_type>(__v));} +#endif + template <class _InputIterator> _LIBCPP_INLINE_VISIBILITY void insert(_InputIterator __f, _InputIterator __l) @@ -1940,6 +1955,15 @@ iterator insert(const_iterator __p, const value_type& __v) {return __tree_.__insert_multi(__p.__i_, __v);} +#if _LIBCPP_STD_VER > 14 && !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) + _LIBCPP_INLINE_VISIBILITY + iterator insert( value_type&& __v) {return __tree_.__insert_multi(_VSTD::forward<value_type>(__v));} + + _LIBCPP_INLINE_VISIBILITY + iterator insert(const_iterator __p, value_type&& __v) + {return __tree_.__insert_multi(__p.__i_, _VSTD::forward<value_type>(__v));} +#endif + template <class _InputIterator> _LIBCPP_INLINE_VISIBILITY void insert(_InputIterator __f, _InputIterator __l) diff --git a/test/std/containers/associative/map/map.modifiers/insert_iter_rv.pass.cpp b/test/std/containers/associative/map/map.modifiers/insert_iter_rv.pass.cpp index 42b41fd..fabafd3 100644 --- a/test/std/containers/associative/map/map.modifiers/insert_iter_rv.pass.cpp +++ b/test/std/containers/associative/map/map.modifiers/insert_iter_rv.pass.cpp
@@ -52,7 +52,7 @@ assert(r->first == 3); assert(r->second == 3); } -#if __cplusplus >= 201103L +#if TEST_STD_VER >= 11 { typedef std::map<int, MoveOnly, std::less<int>, min_allocator<std::pair<const int, MoveOnly>>> M; typedef std::pair<int, MoveOnly> P; @@ -83,5 +83,35 @@ assert(r->second == 3); } #endif +#if TEST_STD_VER > 14 + { + typedef std::map<int, MoveOnly> M; + typedef M::iterator R; + M m; + R r = m.insert(m.end(), {2, MoveOnly(2)}); + assert(r == m.begin()); + assert(m.size() == 1); + assert(r->first == 2); + assert(r->second == 2); + + r = m.insert(m.end(), {1, MoveOnly(1)}); + assert(r == m.begin()); + assert(m.size() == 2); + assert(r->first == 1); + assert(r->second == 1); + + r = m.insert(m.end(), {3, MoveOnly(3)}); + assert(r == prev(m.end())); + assert(m.size() == 3); + assert(r->first == 3); + assert(r->second == 3); + + r = m.insert(m.end(), {3, MoveOnly(3)}); + assert(r == prev(m.end())); + assert(m.size() == 3); + assert(r->first == 3); + assert(r->second == 3); + } #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES +#endif } diff --git a/test/std/containers/associative/map/map.modifiers/insert_rv.pass.cpp b/test/std/containers/associative/map/map.modifiers/insert_rv.pass.cpp index a9d3277..813e425 100644 --- a/test/std/containers/associative/map/map.modifiers/insert_rv.pass.cpp +++ b/test/std/containers/associative/map/map.modifiers/insert_rv.pass.cpp
@@ -11,6 +11,7 @@ // class map +// pair<iterator, bool> insert( value_type&& v); // C++17 and later // template <class P> // pair<iterator, bool> insert(P&& p); @@ -55,7 +56,7 @@ assert(r.first->first == 3); assert(r.first->second == 3); } -#if __cplusplus >= 201103L +#if TEST_STD_VER >= 11 { typedef std::map<int, MoveOnly, std::less<int>, min_allocator<std::pair<const int, MoveOnly>>> M; typedef std::pair<M::iterator, bool> R; @@ -89,5 +90,39 @@ assert(r.first->second == 3); } #endif +#if TEST_STD_VER > 14 + { + typedef std::map<int, MoveOnly> M; + typedef std::pair<M::iterator, bool> R; + M m; + R r = m.insert({2, MoveOnly(2)}); + assert(r.second); + assert(r.first == m.begin()); + assert(m.size() == 1); + assert(r.first->first == 2); + assert(r.first->second == 2); + + r = m.insert({1, MoveOnly(1)}); + assert(r.second); + assert(r.first == m.begin()); + assert(m.size() == 2); + assert(r.first->first == 1); + assert(r.first->second == 1); + + r = m.insert({3, MoveOnly(3)}); + assert(r.second); + assert(r.first == prev(m.end())); + assert(m.size() == 3); + assert(r.first->first == 3); + assert(r.first->second == 3); + + r = m.insert({3, MoveOnly(3)}); + assert(!r.second); + assert(r.first == prev(m.end())); + assert(m.size() == 3); + assert(r.first->first == 3); + assert(r.first->second == 3); + } +#endif #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES } diff --git a/test/std/containers/associative/multimap/multimap.modifiers/insert_iter_rv.pass.cpp b/test/std/containers/associative/multimap/multimap.modifiers/insert_iter_rv.pass.cpp index b44f464..de5aea6 100644 --- a/test/std/containers/associative/multimap/multimap.modifiers/insert_iter_rv.pass.cpp +++ b/test/std/containers/associative/multimap/multimap.modifiers/insert_iter_rv.pass.cpp
@@ -52,7 +52,7 @@ assert(r->first == 3); assert(r->second == 2); } -#if __cplusplus >= 201103L +#if TEST_STD_VER >= 11 { typedef std::multimap<int, MoveOnly, std::less<int>, min_allocator<std::pair<const int, MoveOnly>>> M; typedef std::pair<int, MoveOnly> P; @@ -83,5 +83,36 @@ assert(r->second == 2); } #endif +#if TEST_STD_VER > 14 + { + typedef std::multimap<int, MoveOnly> M; + typedef std::pair<int, MoveOnly> P; + typedef M::iterator R; + M m; + R r = m.insert(m.cend(), {2, MoveOnly(2)}); + assert(r == m.begin()); + assert(m.size() == 1); + assert(r->first == 2); + assert(r->second == 2); + + r = m.insert(m.cend(), {1, MoveOnly(1)}); + assert(r == m.begin()); + assert(m.size() == 2); + assert(r->first == 1); + assert(r->second == 1); + + r = m.insert(m.cend(), {3, MoveOnly(3)}); + assert(r == prev(m.end())); + assert(m.size() == 3); + assert(r->first == 3); + assert(r->second == 3); + + r = m.insert(m.cend(), {3, MoveOnly(2)}); + assert(r == prev(m.end())); + assert(m.size() == 4); + assert(r->first == 3); + assert(r->second == 2); + } +#endif #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES } diff --git a/test/std/containers/associative/multimap/multimap.modifiers/insert_rv.pass.cpp b/test/std/containers/associative/multimap/multimap.modifiers/insert_rv.pass.cpp index b1c0435..86fc6ce 100644 --- a/test/std/containers/associative/multimap/multimap.modifiers/insert_rv.pass.cpp +++ b/test/std/containers/associative/multimap/multimap.modifiers/insert_rv.pass.cpp
@@ -51,7 +51,7 @@ assert(r->first == 3); assert(r->second == 3); } -#if __cplusplus >= 201103L +#if TEST_STD_VER >= 11 { typedef std::multimap<int, MoveOnly, std::less<int>, min_allocator<std::pair<const int, MoveOnly>>> M; typedef M::iterator R; @@ -81,5 +81,35 @@ assert(r->second == 3); } #endif +#if TEST_STD_VER > 14 + { + typedef std::multimap<int, MoveOnly> M; + typedef M::iterator R; + M m; + R r = m.insert({2, MoveOnly(2)}); + assert(r == m.begin()); + assert(m.size() == 1); + assert(r->first == 2); + assert(r->second == 2); + + r = m.insert({1, MoveOnly(1)}); + assert(r == m.begin()); + assert(m.size() == 2); + assert(r->first == 1); + assert(r->second == 1); + + r = m.insert({3, MoveOnly(3)}); + assert(r == prev(m.end())); + assert(m.size() == 3); + assert(r->first == 3); + assert(r->second == 3); + + r = m.insert({3, MoveOnly(3)}); + assert(r == prev(m.end())); + assert(m.size() == 4); + assert(r->first == 3); + assert(r->second == 3); + } +#endif #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES } diff --git a/test/support/MoveOnly.h b/test/support/MoveOnly.h index e4d9f64..b965351 100644 --- a/test/support/MoveOnly.h +++ b/test/support/MoveOnly.h
@@ -17,6 +17,7 @@ class MoveOnly { + friend class MoveOnly2; MoveOnly(const MoveOnly&); MoveOnly& operator=(const MoveOnly&); @@ -34,6 +35,29 @@ bool operator< (const MoveOnly& x) const {return data_ < x.data_;} }; +class MoveOnly2 +{ + MoveOnly2(const MoveOnly&); + MoveOnly2& operator=(const MoveOnly2&); + + int data_; +public: + MoveOnly2(int data = 1) : data_(data) {} + MoveOnly2(MoveOnly2&& x) + : data_(x.data_) {x.data_ = 0;} + MoveOnly2& operator=(MoveOnly2&& x) + {data_ = x.data_; x.data_ = 0; return *this;} + MoveOnly2(MoveOnly&& x) + : data_(x.data_) {x.data_ = 0;} + MoveOnly2& operator=(MoveOnly&& x) + {data_ = x.data_; x.data_ = 0; return *this;} + + int get() const {return data_;} + + bool operator==(const MoveOnly2& x) const {return data_ == x.data_;} + bool operator< (const MoveOnly2& x) const {return data_ < x.data_;} +}; + namespace std { template <> @@ -43,6 +67,12 @@ std::size_t operator()(const MoveOnly& x) const {return x.get();} }; +template <> +struct hash<MoveOnly2> + : public std::unary_function<MoveOnly, std::size_t> +{ + std::size_t operator()(const MoveOnly2& x) const {return x.get();} +}; } #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 